The Other QMC

Quasi-Monte Carlo is the other method commonly referred to by the QMC acronym (I will abbreviate it QuasiMC to minimize confusion). It's not really Monte Carlo since the sequence of points is not random, but the point sets do have a Monte Carlo-ish feel about them.

And in fact, it does share the property of arbitrary termination with Monte Carlo integration (consider a grid - you have have use all the points at a particular spacing. Stopping half way across the region of integration is not going to yield good results).

The reason people are interested in QuasiMC is that its convergence is better than the 1/sqrt(N) of Monte Carlo. It does this by using point sets that are more evenly distributed than random points - there are fewer clumps of points or large gaps that appear in random sequences (Search for 'Low-discrepancy sequences'. Here's the Wikipedia entries for a technical discussion and some sequences).

QuasiMC point sets are usually generated from sequences where the low-discrepancy condition can be verified theoretically, but it is possible to use the intuitive approach of making the points maximally spread out (see this presentation for an example).

The following algorithm will generate a set of N points that gives better convergence than random (at least it worked on a simple integrand in one dimension.)

1. compute some random points (>> N points)


2. pick a starting point and put it in the set S.


3. find the point that is the furthest from all existing points in S, and place that point in S.


4. repeat the step 3 until N points are selected.

(I'm not saying this an efficient way to generate the points, just that it can be done.)

For addition information, see also chapter 7.7 in Numerical Recipes